All Questions
Tagged with dynamic-programmingmemoization
16 questions
5votes
3answers
962views
LeetCode 678: Valid Parenthesis String, Recursion memoization to DP
How can the following recursion + memoization code be converted into a tabulation format dynamic programming solution? The code is working, but I want to improve it. The challenge I am facing is ...
4votes
1answer
117views
Calculate optimal game upgrades, v2
This is the second iteration of the code I originally posted here: Calculate optimal game upgrades. Based on the feedback there, I chose to change the code to use a dynamic programming approach with ...
- 83
1vote
1answer
598views
Leetcode: 2327. Number of People Aware of a Secret
On day 1, one person discovers a secret. You are given an integer delay, which means that each person will share the secret with a new person every day, starting from delay days after discovering the ...
- 21
2votes
1answer
194views
k-dice Ways to get a target value
I'm trying to solve the following problem: You have a k-dice. A k-dice is a dice which have k-faces and each face have value written from 1 to k. Eg. A 6-dice is the normal dice we use while playing ...
- 222
3votes
1answer
319views
Efficiently calculate value of Pascal's Triangle using memoization and recursion
So reading about functional programming, applications to dynamic programming, and learning Scala. I figured I would try it out with a popular example, Pascal's Triangle, tests against known values ...
- 133
2votes
2answers
216views
Knapsack performance issue
I'm solving a knapsack problem here. It works, but gives time limit exceeds on a certain test case. Problem statement There are N items, numbered 1,2,…,N. For each i (1≤i≤N), Item i has a weight of ...
- 167
1vote
1answer
636views
CodeChef Matches challenge
I am solving some problems from CodeChef but I am stuck on the Matches problem: Ari and Rich are playing a pretty confusing game. Here are the rules of the game: The game is played with ...
2votes
1answer
64views
Number of way to render an amount of money
I made an algorithm to train my skill in dynamic programming and I would like to have feed back on it. This algorithm takes a money system (int) and have a certain ...
3votes
0answers
2kviews
Robot on a Grid: Find a path between two corners with forbidden cells on the road
Problem statement The problem is defined in the book as following: 8.2 Robot in a Grid Imagine a robot sitting on the upper left corner of grid with r rows and <...
- 3,520
2votes
1answer
87views
Dynamic programming to solve two printers with different speeds
I solved this problem using a Class, but thought I might try to figure out this memoization thing. Problem There are two printers that print pages at different speeds (X, Y). What is the minimum ...
- 7,249
2votes
1answer
240views
Check the equality for each subset of a string S against the target T and return a count
I wrote the following code to solve this leetcode problem: ...
2votes
1answer
105views
Optimally allocating a resource with time-varying demand and cost
I'm working on the following DP which finds the optimal way to allocate a resource. At each time step I can either allocate (0.2 resources) at cost C or not in which case the storage is reduced by the ...
- 123
10votes
3answers
4kviews
Find the Nth number divisible by only 2,3,5, or 7
I recently participated in a small friendly competition and this was one of the questions: A number whose only prime factors are 2, 3, 5 or 7 is called a humble number. The first 20 humble numbers ...
- 203
2votes
1answer
2kviews
Implementation of Longest Common Subsequence
So I implemented the LCS algorithm once using a 2-D matrix to store values while the other one used a python dictionary. I found the dictionary implementation was easier to implement and was a more ...
- 65
4votes
1answer
590views
Google CodeJam Round D APAC Test
Problem A: Vincenzo decides to make cube IV but only has the budget to make a square maze. Its a perfect maze, every room is in the form of a square and there are 4 doors (1 on each side of the room)...
- 201
